package com.sun.javaalgorithm.day01;

/**
 * @version 1.0
 * @Package: com.sun.javaalgorithm.day01
 * @ClassName: erfen01
 * @Author: sgq
 * @Date: 2024/4/7 17:48
 * @Description: 二分查找相关
 */
public class BinarySearch {

    /**
     * 二分法查找- j在可选范围内【基础版】
     *
     * @param arr
     * @return
     */
    public static int sort1(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (arr[mid] < target) {
                i = mid + 1;
            } else if (arr[mid] > target) {
                j = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分法查找 - j不在可选范围内
     *
     * @param arr
     * @return
     */
    public static int sort2(int[] arr, int target) {
        int i = 0;
        int j = arr.length;
        while (i < j) {
            int mid = (i + j) >>> 1;
            if (arr[mid] == target) {
                return mid;
            } else if (target < arr[mid]) {
                j = mid;
            } else {
                i = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 二分法查找 - 平衡二分查找
     *
     * @param arr
     * @return
     */
    public static int sort3(int[] arr, int target) {
        int i = 0;
        int j = arr.length;
        while (1 < j - i) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid;
            } else {
                i = mid;
            }
            // 错误写法
//            if (target > arr[mid]) {
//                i = mid;
//            } else {
//                j = mid;
//            }
        }
        if (arr[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    /**
     * 二分法查找 - 存在多个目标数据，获取最左侧的
     *
     * @param arr
     * @return
     */
    public static int sortLeftmost(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (arr[mid] < target) {
                i = mid + 1;
            } else if (arr[mid] > target) {
                j = mid - 1;
            } else {
                candidate = mid;
                j = mid - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分法查找 - 存在多个目标数据，获取最右侧的
     *
     * @param arr
     * @return
     */
    public static int sortRightmost(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (arr[mid] < target) {
                i = mid + 1;
            } else if (arr[mid] > target) {
                j = mid - 1;
            } else {
                candidate = mid;
                i = mid + 1;
            }
        }
        return candidate;
    }





    public static void main(String[] args) {
//        int[] arr = {1, 2, 5, 45, 63, 89, 105, 225, 459, 698, 888};
//        System.out.println(sort1(arr, 1));
//        System.out.println(sort1(arr, 698));
//        System.out.println(sort1(arr, 666));
//
//        System.out.println(sort2(arr, 1));
//        System.out.println(sort2(arr, 698));
//        System.out.println(sort2(arr, 666));
//
//        int[] arr1 = {1, 2, 5, 45, 63};
//        System.out.println(sort3(arr1, 1));
//        System.out.println(sort3(arr1, 5));
//        System.out.println(sort3(arr1, 63));
//        System.out.println(sort3(arr1, 66));

        int[] arr2 = {1, 2, 5, 5, 5, 5, 5, 63};
        System.out.println(sortLeftmost(arr2, 5));
        System.out.println(sortRightmost(arr2, 5));
    }

}
